/*
 * @lc app=leetcode.cn id=287 lang=cpp
 *
 * [287] 寻找重复数
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int l = 0,r = nums.size()-1;
        while(l < r) {
            int mid = ((r + l)/2);
            int cnt = 0;
            for(int i = 0;i < nums.size();i++) {
                if(nums[i] <= mid) {
                    cnt++;
                }
            }
            if(cnt <= mid) {
                l = mid+1;
            }else if(cnt > mid) {
                r = mid;
            }
        }
        return l;
    }
};
// @lc code=end

